/**
 * 给定总玩家数 n，以及按 [玩家编号,对应可传递玩家编号] 关系组成的二维数组 relation。
 * 返回信息从小 A (编号 0 ) 经过 k 轮传递到编号为 n-1 的小伙伴处的方案数；若不能到达，返回 0。
 **/

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

/**
 * Solution 1:BFS广度优先
 **/
class Solution {
public:
    int numWays(int n, vector<vector<int>>& relation, int k) {
        // 预处理每个顶点能到达的边的集合
        // 用二维vector存储每一个节点能到达的其他节点
        vector<vector<int>> edges(n);
        // 遍历relation中的可传递关系，整理出边的可达到关系
        for(auto & edge : relation){
            int src = edge[0], dst = edge[1];
            edges[src].emplace_back(dst);
        }

        // 初始化步数为0，这样能和轮数k对应
        int step = 0;

        // 初始化辅助队列，把初始玩家编号加入队列
        queue<int> Q;
        Q.push(0);
        // 当传递轮数未到指定轮数前
        while (Q.size() && step < k)
        {
            // 轮数+1
            step ++;
            // 对于当前轮传递到的玩家，从队列中弹出，并将它们可到达的玩家节点加入队列
            for(int i=0; i<Q.size(); i++){
                int tmp = Q.front();
                Q.pop();
                for(auto & next : edges[tmp]){
                    Q.push(next);
                }
            }
        }

        // way存储最后结果
        int way = 0;
        if(step == k) {
            while (Q.size())
            {
                if(Q.front() == n-1){
                    way ++;
                }
                Q.pop();
            }
            
        }
        return way;
    }
};